import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(root, 1));
        int maxLen = -1;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            int start = 0;
            int end = 0;
            for (int i = 0; i < sz; i++) {
                Pair pair = queue.poll();
                TreeNode node = pair.node;
                int index = pair.index;

                if (i == 0) start = index;
                if (i == sz - 1) end = index;

                if (node.left != null) queue.add(new Pair(node.left, 2 * index));
                if (node.right != null) queue.add(new Pair(node.right, 2 * index + 1));
            }
            int len = end - start + 1;
            maxLen = len > maxLen ? len : maxLen;
        }
        return maxLen;
    }

    private class Pair {
        TreeNode node;
        int index;
        Pair(TreeNode node, int index) {
            this.node = node;
            this.index = index;
        }
    }
}